This section endeavors to supply a context or background for the various exemplary embodiments of the invention as recited in the claims. The content herein may comprise subject matter that could be utilized, but not necessarily matter that has been previously utilized, described or considered. Unless indicated otherwise, the content described herein is not considered prior art, and should not be considered as admitted prior art by inclusion in this section.
Encryption schemes that support operations on encrypted data (aka homomorphic encryption) have a very wide range of applications in cryptography. This concept was introduced by Rivest et al. shortly after the discovery of public key cryptography [21], and many known public-key cryptosystems support either addition or multiplication of encrypted data. However, supporting both at the same time seems harder, and until recently attempts at constructing so-called “fully homomorphic” encryption turned out to be insecure.